<!DOCTYPE html>



  


<html class="theme-next pisces use-motion" lang="zh-Hans">
<head>
  <!-- hexo-inject:begin --><!-- hexo-inject:end --><meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>
<meta name="theme-color" content="#222">









<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />
















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css" />







<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />

<link href="/css/main.css?v=5.1.3" rel="stylesheet" type="text/css" />


  <link rel="apple-touch-icon" sizes="180x180" href="/images/avatar.jpg?v=5.1.3">


  <link rel="icon" type="image/png" sizes="32x32" href="/images/avatar.jpg?v=5.1.3">


  <link rel="icon" type="image/png" sizes="16x16" href="/images/avatar.jpg?v=5.1.3">


  <link rel="mask-icon" href="/images/avatar.jpg?v=5.1.3" color="#222">





  <meta name="keywords" content="算法,Algorithms Notes," />










<meta name="description" content="1 基础编程模型Java 四类八种类型 整型：byte, short, int, long 浮点型：float, double 布尔型：boolean 字符型：char  1234567891011121314151617public static int binarySearch(int[] a, int key)&amp;#123;    int left = 0;    int right = a.">
<meta name="keywords" content="算法,Algorithms Notes">
<meta property="og:type" content="article">
<meta property="og:title" content="（一）基础（Fundamentals）：数据结构">
<meta property="og:url" content="http://fighterhit.github.io/2017/12/27/algorithm_and_datastructure/Algorithms4/Ch1-Fundamentals/index.html">
<meta property="og:site_name" content="Fighter&#39;s Blog">
<meta property="og:description" content="1 基础编程模型Java 四类八种类型 整型：byte, short, int, long 浮点型：float, double 布尔型：boolean 字符型：char  1234567891011121314151617public static int binarySearch(int[] a, int key)&amp;#123;    int left = 0;    int right = a.">
<meta property="og:locale" content="zh-Hans">
<meta property="og:updated_time" content="2018-01-29T11:41:49.446Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="（一）基础（Fundamentals）：数据结构">
<meta name="twitter:description" content="1 基础编程模型Java 四类八种类型 整型：byte, short, int, long 浮点型：float, double 布尔型：boolean 字符型：char  1234567891011121314151617public static int binarySearch(int[] a, int key)&amp;#123;    int left = 0;    int right = a.">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Pisces',
    version: '5.1.3',
    sidebar: {"position":"left","display":"post","offset":12,"b2t":false,"scrollpercent":false,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: '博主'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="http://fighterhit.github.io/2017/12/27/algorithm_and_datastructure/Algorithms4/Ch1-Fundamentals/"/>





  <title>（一）基础（Fundamentals）：数据结构 | Fighter's Blog</title><!-- hexo-inject:begin --><!-- hexo-inject:end -->
  








</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">

  
  
    
  

  <!-- hexo-inject:begin --><!-- hexo-inject:end --><div class="container sidebar-position-left page-post-detail">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/"  class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">Fighter's Blog</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <p class="site-subtitle">深度沉迷学习</p>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br />
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/about/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-user"></i> <br />
            
            关于
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br />
            
            标签
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br />
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br />
            
            归档
          </a>
        </li>
      

      
    </ul>
  

  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://fighterhit.github.io/2017/12/27/algorithm_and_datastructure/Algorithms4/Ch1-Fundamentals/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="Fighter.">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Fighter's Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">（一）基础（Fundamentals）：数据结构</h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-12-27T14:21:56+08:00">
                2017-12-27
              </time>
            

            

            
          </span>

          
            <span class="post-category" >
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/算法与数据结构/" itemprop="url" rel="index">
                    <span itemprop="name">算法与数据结构</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          
            <span class="post-meta-divider">|</span>
            <span class="page-pv"><i class="fa fa-file-o"></i>
            <span class="busuanzi-value" id="busuanzi_value_page_pv" ></span>
            </span>
          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        <h2 id="1-基础编程模型"><a href="#1-基础编程模型" class="headerlink" title="1 基础编程模型"></a>1 基础编程模型</h2><h3 id="Java-四类八种类型"><a href="#Java-四类八种类型" class="headerlink" title="Java 四类八种类型"></a>Java 四类八种类型</h3><ul>
<li>整型：byte, short, int, long</li>
<li>浮点型：float, double</li>
<li>布尔型：boolean</li>
<li>字符型：char</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div></pre></td><td class="code"><pre><div class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">int</span> <span class="title">binarySearch</span><span class="params">(<span class="keyword">int</span>[] a, <span class="keyword">int</span> key)</span></span>&#123;</div><div class="line">    <span class="keyword">int</span> left = <span class="number">0</span>;</div><div class="line">    <span class="keyword">int</span> right = a.length - <span class="number">1</span>;</div><div class="line">    <span class="keyword">while</span>(left &lt;= right)&#123;</div><div class="line">        <span class="keyword">int</span> mid = left + ((right - left) &gt;&gt;<span class="number">1</span>);</div><div class="line">        <span class="keyword">if</span>(a[mid] &gt; key)&#123;</div><div class="line">            right = mid -<span class="number">1</span>;</div><div class="line">        &#125;</div><div class="line">        <span class="keyword">else</span> <span class="keyword">if</span>(a[mid] &lt; key)&#123;</div><div class="line">            left = mid + <span class="number">1</span>;</div><div class="line">        &#125;</div><div class="line">        <span class="keyword">else</span>&#123;</div><div class="line">            <span class="keyword">return</span> mid;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">return</span> -<span class="number">1</span>;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<h3 id="数组"><a href="#数组" class="headerlink" title="数组"></a>数组</h3><ol>
<li><p>颠倒数组中元素顺序</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div></pre></td><td class="code"><pre><div class="line"><span class="comment">//注意 n 值、for 循环边界、以及循环体内 n - 1 - i</span></div><div class="line"><span class="keyword">int</span> n = a.length;</div><div class="line"><span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n/<span class="number">2</span>; i++)&#123;</div><div class="line">    <span class="keyword">int</span> temp = a[i];</div><div class="line">    a[i] = a[n - <span class="number">1</span> - i];</div><div class="line">    a[i - <span class="number">1</span> - i] = temp;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
</li>
<li><p>矩阵相乘</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div></pre></td><td class="code"><pre><div class="line"><span class="comment">//假设a[n][n], b[n][n], c[n][n]</span></div><div class="line"><span class="keyword">int</span> n = a.length;</div><div class="line"><span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++)&#123;</div><div class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; n; j++)&#123;</div><div class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> k = <span class="number">0</span>; k &lt; n; k++)&#123;</div><div class="line">            c[i][j] += a[i][k] * b[k][j];</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
</li>
</ol>
<a id="more"></a>
<h3 id="静态方法"><a href="#静态方法" class="headerlink" title="静态方法"></a>静态方法</h3><ul>
<li>判断一个数是否为素数</li>
</ul>
<blockquote>
<p>一个数若可以进行因数分解，那么分解时得到的两个数一定是<strong>一个小于等于sqrt(n)</strong>，<strong>一个大于等于sqrt(n)</strong>，据此，代码中不需要遍历到n-1，遍历到sqrt(n)即可，因为若sqrt(n)左侧找不到约数，那么右侧也一定找不到约数。</p>
</blockquote>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div></pre></td><td class="code"><pre><div class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">boolean</span> <span class="title">isPrime</span><span class="params">(<span class="keyword">int</span> n)</span></span>&#123;</div><div class="line">    <span class="comment">//小于2直接返回false</span></div><div class="line">    <span class="keyword">if</span>(n &lt; <span class="number">2</span>)&#123;</div><div class="line">        <span class="keyword">return</span> <span class="keyword">false</span>;</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">2</span>; i * i &lt;= n; i++)&#123;</div><div class="line">        <span class="keyword">if</span> (n % i == <span class="number">0</span>)&#123;</div><div class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</div><div class="line">        &#125;<span class="keyword">else</span>&#123;</div><div class="line">            <span class="keyword">return</span> <span class="keyword">true</span>;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<ul>
<li>计算平方根（牛顿迭代法）<br>  <a href="https://www.guokr.com/question/461510/" target="_blank" rel="noopener">牛顿开方法的算法及其原理</a></li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div></pre></td><td class="code"><pre><div class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">double</span> <span class="title">sqrt</span><span class="params">(<span class="keyword">double</span> c)</span></span>&#123;</div><div class="line">    <span class="keyword">if</span>(c &lt; <span class="number">0</span>)&#123;</div><div class="line">        <span class="keyword">return</span> Double.NaN;</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">double</span> err = <span class="number">1e-15</span>;</div><div class="line">    <span class="keyword">double</span> t = c;</div><div class="line">    <span class="comment">// 1 - c/t^2 &gt; err 两边同乘 t</span></div><div class="line">    <span class="keyword">while</span>(Math.abs(t - c / t) &gt; err * t)&#123;</div><div class="line">        t = (t + c / t) / <span class="number">2</span>;</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">return</span> t;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<blockquote>
<p>方法的性质——参数按值传递：方法中改变一个参数变量的值对调用者没有影响，也意味着数组参数将是原数组别名——方法中使用的参数变量能引用调用者的数组并改变其内容。</p>
</blockquote>
<p><strong>递归</strong>：</p>
<p>递归三个重要性质：</p>
<ol>
<li>递归总有一个最简单情况——方法第一条语句总是一个包含return的条件语句。</li>
<li>递归调用总是尝试解决一个规模更小的子问题，这样递归才能收敛到最简单的情况。</li>
<li>递归调用的父问题和尝试解决的子问题之间不应该有交集。</li>
</ol>
<h3 id="输入输出"><a href="#输入输出" class="headerlink" title="输入输出"></a>输入输出</h3><p><strong>重定向和管道</strong>：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div></pre></td><td class="code"><pre><div class="line"><span class="comment">//模型：RandomSeq -&gt; 标准输出 -&gt; data.txt</span></div><div class="line">java RandomSeq <span class="number">1000</span> <span class="number">2000.0</span> &gt; data.txt</div><div class="line"><span class="comment">//模型：data.txt -&gt; 标准输入 -&gt; Average</span></div><div class="line">java Average &lt; data.txt</div><div class="line"><span class="comment">//模型：RandomSeq -&gt; 标准输出 -&gt; 标准输入 -&gt; Average</span></div><div class="line">java RandomSeq <span class="number">1000</span> <span class="number">2000.0</span> | java Average</div></pre></td></tr></table></figure>
<h3 id="Q-amp-A"><a href="#Q-amp-A" class="headerlink" title="Q&amp;A"></a>Q&amp;A</h3><ol>
<li>如何将double变量初始化为无穷大？<br> <code>Double.POSITIVE_INFINITY</code>（1.0/0.0） 和 <code>Double.NEGTIVE_INFINITY</code>（-1.0/0.0）</li>
<li>Java表达式 1/0 和 1.0/0.0 值分别是？<br> 第一个表达式产生一个运行时除零异常（会终止程序，因为该值未定义）;第二个表达式值是 Infinity（无穷大，JDK内部定义 1.0/0.0为正无穷大，-1.0/0.0为负无穷大）。</li>
<li>负数除法和余数的结果是什么？<br> 表达式 a/b 的商会向 0 取整；a % b 的余数定义为 (a/b)*b + a%b 恒等于 a。例如 -14/3 和 14/-3 的 商都是-4，但-14 % 3 是 -2，而14 % -3 是 2。</li>
</ol>
<h2 id="2-数据抽象"><a href="#2-数据抽象" class="headerlink" title="2 数据抽象"></a>2 数据抽象</h2><h3 id="使用抽象数据类型"><a href="#使用抽象数据类型" class="headerlink" title="使用抽象数据类型"></a>使用抽象数据类型</h3><p><strong>继承的方法</strong><br>Java 中的所有数据类型都会继承 toString() 方法来返回 String 表示的该类型的值。Java 会在用 + 运算符将任意数据类型的值和 String 值连接时调用该方法。该方法的默认实现并不实用（它会返回用字符串表示的该数据类型值的内存地址），因此常常会提供实现来重载默认实现，并在此时在 API 中加上 toString() 方法。此类方法还有 equals()、compareTo() 和 hashCode()。</p>
<h3 id="抽象数据类型举例"><a href="#抽象数据类型举例" class="headerlink" title="抽象数据类型举例"></a>抽象数据类型举例</h3><ol>
<li><p>判断字符串是否是回文</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div></pre></td><td class="code"><pre><div class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">boolean</span> <span class="title">isPalindrome</span><span class="params">(String s)</span></span>&#123;</div><div class="line">    <span class="keyword">int</span> n = s.length;</div><div class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n/<span class="number">2</span>; i++)&#123;</div><div class="line">        <span class="keyword">if</span>(s.charAt(i) != s.charAt(n - <span class="number">1</span> - i))</div><div class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">return</span> <span class="keyword">true</span>;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
</li>
<li><p>从命令行参数中提取文件名和扩展名</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div></pre></td><td class="code"><pre><div class="line">String s = arg[<span class="number">0</span>];</div><div class="line"><span class="keyword">int</span> dot = s.indexOf(<span class="string">"."</span>);</div><div class="line">String base = s.subString(<span class="number">0</span>, dot);</div><div class="line">String extension = s.subString(dot + <span class="number">1</span>, s.length());</div></pre></td></tr></table></figure>
</li>
<li><p>检查一个字符串数组中元素是否已按照字母表顺序排列</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div></pre></td><td class="code"><pre><div class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isSotred</span><span class="params">(String[] a)</span></span>&#123;</div><div class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; a.length; i++)&#123;</div><div class="line">        <span class="keyword">if</span>(a[i - <span class="number">1</span>].compareTo(a[i]) &gt; <span class="number">0</span>)&#123;</div><div class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">return</span> <span class="keyword">true</span>;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
</li>
</ol>
<blockquote>
<p>a.compareTo(b)：比较a和b的ascii码值，</p>
<ul>
<li>a &lt; b：返回 -1 （即前面小于后面）</li>
<li>a = b：返回 0 （即前后相等）  </li>
<li>a &gt; b：返回 1 （即前面大于后面）</li>
</ul>
</blockquote>
<h3 id="数据类型的设计"><a href="#数据类型的设计" class="headerlink" title="数据类型的设计"></a>数据类型的设计</h3><p><strong>等价性</strong></p>
<p>Java 约定 equals() 必须是一种等价性关系。它必须具有：</p>
<ul>
<li>自反性：x.equals(x) 为 true</li>
<li>对称性：当且仅当 y.equals(x) 为 true 时，x.equals(y) 也将为true</li>
<li>传递性：如果 x.equals(y) 和 y.equals(z) 均为 true 时，x.equals(z) 也将为 true</li>
</ul>
<p>另外，它必须接受一个 Object 为参数并满足以下性质：</p>
<ul>
<li>一致性：当两个对象均未被修改时，反复调用 x.equals(y) 总是会返回相同的值；</li>
<li>非空性：x.equals(null) 总是返回 false</li>
</ul>
<p><strong>不可变性</strong></p>
<p>Java 数组（可变），String 类型（不可变）<br>不可变性的缺点：</p>
<ul>
<li>需要为每个值创建一个新对象，这种开销一般可以接受，因为 Java 的垃圾回收器通常都为此进行了优化。</li>
<li>final 只能保证原始数据类型的实例变量的不可变，无法用于引用类型的变量。如果一个引用类型的实例变量含有修饰符 final，该实例变量的值（某个对象的引用）就永远无法改变了——将永远指向同一个对象,但对象的值本身仍然可变。</li>
</ul>
<h2 id="3-背包、队列和栈"><a href="#3-背包、队列和栈" class="headerlink" title="3 背包、队列和栈"></a>3 背包、队列和栈</h2><p>许多基础数据类型都和对象集合有关。接下来将学习三种数据类型：背包（Bag）、队列（Queue）和栈（Stack）。它们不同之处在于删除或访问对象的顺序不同。</p>
<h3 id="API"><a href="#API" class="headerlink" title="API"></a>API</h3><p>每份API都含有一个<strong>无参的构造函数、一个向集合添加单个元素的方法、一个测试集合是否为空的方法和一个返回集合大小</strong>的方法。</p>
<div class="table-container">
<table>
<thead>
<tr>
<th style="text-align:center">背包</th>
<th></th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center"> <code>public class Bag&lt;Item&gt; implements Iterable&lt;Item&gt;</code></td>
<td></td>
</tr>
<tr>
<td style="text-align:center"> Bag()</td>
<td>创建一个空背包</td>
</tr>
<tr>
<td style="text-align:center"> void add(Item item)</td>
<td>添加一个元素</td>
</tr>
<tr>
<td style="text-align:center"> boolean isEmpty()</td>
<td>背包是否为空</td>
</tr>
<tr>
<td style="text-align:center"> int size()</td>
<td>背包中的元素数量</td>
</tr>
</tbody>
</table>
</div>
<hr>
<div class="table-container">
<table>
<thead>
<tr>
<th style="text-align:center">先进先出(FIFO)队列</th>
<th></th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center"> <code>public class Queue&lt;Item&gt; implements Iterable&lt;Item&gt;</code></td>
<td></td>
</tr>
<tr>
<td style="text-align:center"> Queue()</td>
<td>创建一个空队列</td>
</tr>
<tr>
<td style="text-align:center"> void enqueue(Item item)</td>
<td>添加一个元素</td>
</tr>
<tr>
<td style="text-align:center"> boolean isEmpty()</td>
<td>队列是否为空</td>
</tr>
<tr>
<td style="text-align:center"> int size()</td>
<td>队列中的元素数量</td>
</tr>
<tr>
<td style="text-align:center"> Item dequeue()</td>
<td>删除最近添加的元素</td>
</tr>
</tbody>
</table>
</div>
<hr>
<div class="table-container">
<table>
<thead>
<tr>
<th style="text-align:center">下压（后进先出，LIFO）栈</th>
<th></th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center"> <code>public class Stack&lt;Item&gt; implements Iterable&lt;Item&gt;</code></td>
<td></td>
</tr>
<tr>
<td style="text-align:center"> Stack()</td>
<td>创建一个空栈</td>
</tr>
<tr>
<td style="text-align:center"> void push(Item item)</td>
<td>添加一个元素</td>
</tr>
<tr>
<td style="text-align:center"> boolean isEmpty()</td>
<td>栈是否为空</td>
</tr>
<tr>
<td style="text-align:center"> int size()</td>
<td>栈中的元素数量</td>
</tr>
<tr>
<td style="text-align:center"> Item pop()</td>
<td>删除最近添加的元素</td>
</tr>
</tbody>
</table>
</div>
<p>下面介绍一个用栈和泛型的经典例子。</p>
<h4 id="举例：算术表达式求值"><a href="#举例：算术表达式求值" class="headerlink" title="举例：算术表达式求值"></a>举例：算术表达式求值</h4><p>(1 + ((2 + 3) * (4 * 5))) </p>
<blockquote>
<p>表达式由括号、运算符和操作数（数字）组成，<strong>用两个栈</strong>，根据以下4种情况从左到右逐个将这些实数送入栈处理。</p>
</blockquote>
<ol>
<li>将<strong>操作数</strong>压入操作数栈</li>
<li>将<strong>运算符</strong>压入运算符栈</li>
<li>忽略<strong>左括号</strong></li>
<li>遇到<strong>右括号</strong>时，弹出一个运算符，弹出所需数量的操作数，并将运算符和操作数的运算结果压入操作数栈</li>
<li>处理完<strong>最后一个右括号</strong>时，操作数栈上只会有一个值，它就是表达式的值</li>
</ol>
<blockquote>
<p>简要证明：每当算法遇到一个被括号包围并由一个运算符和两个操作数组成的子表达式时，它都将运算符和操作数的计算结果压入操作数栈，这样结果就好像在输入中用这个值代替了该子表达式，因此用这个值代替子表达式得到的结果和原表达式相同，可以反复应用这个规律并得到一个最终值。</p>
</blockquote>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div></pre></td><td class="code"><pre><div class="line"><span class="comment">// Dijkstra 的双栈算术表达式求值算法</span></div><div class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">Evaluate</span></span>&#123;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">main</span><span class="params">(String[] args)</span></span>&#123;</div><div class="line">        Stack&lt;String&gt; ops = <span class="keyword">new</span> Stack&lt;String&gt;();</div><div class="line">        Stack&lt;Double&gt; vals = <span class="keyword">new</span> Stack&lt;Double&gt;();</div><div class="line">        <span class="keyword">while</span>(!StdIn.isEmpty())&#123;</div><div class="line">            String s = StdIn.readString();</div><div class="line">            <span class="keyword">if</span>(s.equals(<span class="string">"("</span>));</div><div class="line">            <span class="keyword">else</span> <span class="keyword">if</span>(s.equals(<span class="string">"+"</span>)) ops.push(s);</div><div class="line">            <span class="keyword">else</span> <span class="keyword">if</span>(s.equals(<span class="string">"-"</span>)) ops.push(s);</div><div class="line">            <span class="keyword">else</span> <span class="keyword">if</span>(s.equals(<span class="string">"*"</span>)) ops.push(s);</div><div class="line">            <span class="keyword">else</span> <span class="keyword">if</span>(s.equals(<span class="string">"/"</span>)) ops.push(s);</div><div class="line">            <span class="keyword">else</span> <span class="keyword">if</span>(s.equals(<span class="string">"sqrt"</span>)) ops.push(s);</div><div class="line">            <span class="keyword">else</span> <span class="keyword">if</span>(s.equals(<span class="string">")"</span>))&#123;</div><div class="line">                String op = ops.pop();</div><div class="line">                <span class="keyword">double</span> v = vals.pop();</div><div class="line">                <span class="keyword">if</span>(op.equals(<span class="string">"+"</span>)) v = vals.pop() + v;</div><div class="line">                <span class="keyword">else</span> <span class="keyword">if</span>(op.equals(<span class="string">"-"</span>)) v = vals.pop() - v;</div><div class="line">                <span class="keyword">else</span> <span class="keyword">if</span>(op.equals(<span class="string">"*"</span>)) v = vals.pop() * v;</div><div class="line">                <span class="keyword">else</span> <span class="keyword">if</span>(op.equals(<span class="string">"/"</span>)) v = vals.pop() / v;</div><div class="line">                <span class="keyword">else</span> <span class="keyword">if</span>(op.equals(<span class="string">"sqrt"</span>)) v = Math.sqrt(v);</div><div class="line">                vals.push(v);</div><div class="line">            &#125;<span class="keyword">else</span>&#123;</div><div class="line">                vals.push(Double.parseDouble(s));</div><div class="line">            &#125;</div><div class="line">        &#125;</div><div class="line">        StdOut.println(vals.pop());</div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<blockquote>
<p>这段 Stack 的用例使用了两个栈来计算表达式的值。它展示了一种重要的计算模型：将一个字符串解释为一段程序并执行该程序得到结果。简单起见，这段代码假设表达式没有省略任何括号，数字和字符均以空白字符相隔。</p>
</blockquote>
<h3 id="集合数据类型的实现"><a href="#集合数据类型的实现" class="headerlink" title="集合数据类型的实现"></a>集合数据类型的实现</h3><h4 id="1-定容栈"><a href="#1-定容栈" class="headerlink" title="1 定容栈"></a>1 定容栈</h4><blockquote>
<p>说明：定容栈只支持 String 值，要求用例指定一个容量且不支持迭代。</p>
</blockquote>
<p>实现一份API第一步就是<strong>选择数据的表示方式</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">FixedCapacityStackOfStrings</span></span>&#123;</div><div class="line">    <span class="keyword">private</span> String[] a;</div><div class="line">    <span class="keyword">private</span> <span class="keyword">int</span> N;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="title">FixedCapacityStackOfStrings</span><span class="params">(<span class="keyword">int</span> cap)</span></span>&#123;</div><div class="line">        a = <span class="keyword">new</span> String[cap];</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">push</span><span class="params">(String item)</span></span>&#123;</div><div class="line">        a[N++] = item;</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> String <span class="title">pop</span><span class="params">()</span></span>&#123;</div><div class="line">        <span class="keyword">return</span> a[--N];</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isEmpty</span><span class="params">()</span></span>&#123;</div><div class="line">        <span class="keyword">return</span> N == <span class="number">0</span>;</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">size</span><span class="params">()</span></span>&#123;</div><div class="line">        <span class="keyword">return</span> N;</div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<h4 id="2-进一步：泛型栈"><a href="#2-进一步：泛型栈" class="headerlink" title="2 进一步：泛型栈"></a>2 进一步：泛型栈</h4><blockquote>
<p>把所有 String 都替换为 Item。Item 是一个<strong>类型参数</strong>，在实现时无须知道Item实际类型，只要用例在创建栈时提供具体数据类型就可以。<strong>实际类型必须是引用类型</strong>，用例可以靠自动装箱将原始类型转换为相应的封装类型。另外一个重要细节是我们希望实现一个<strong>泛型数组</strong>：<code>a = new Item[cap]</code>，但 <strong>Java中不允许创建泛型数组</strong>！因此，需要使用类型转换：<code>a = (Item[]) new Object[cap];</code>（Java系统库中类似抽象数据类型的实现也使用了相同的方式）。</p>
</blockquote>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">FixedCapacityStackOfStrings</span>&lt;<span class="title">Item</span>&gt;</span>&#123;</div><div class="line">    <span class="keyword">private</span> Item[] a;</div><div class="line">    <span class="keyword">private</span> <span class="keyword">int</span> N;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="title">FixedCapacityStackOfStrings</span><span class="params">(<span class="keyword">int</span> cap)</span></span>&#123;</div><div class="line">        a = (Item[]) <span class="keyword">new</span> Object[cap];</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">push</span><span class="params">(Item item)</span></span>&#123;</div><div class="line">        a[N++] = item;</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> Item <span class="title">pop</span><span class="params">()</span></span>&#123;</div><div class="line">        <span class="keyword">return</span> a[--N];</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isEmpty</span><span class="params">()</span></span>&#123;</div><div class="line">        <span class="keyword">return</span> N == <span class="number">0</span>;</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">size</span><span class="params">()</span></span>&#123;</div><div class="line">        <span class="keyword">return</span> N;</div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<h4 id="3-动态调整栈大小"><a href="#3-动态调整栈大小" class="headerlink" title="3 动态调整栈大小"></a>3 动态调整栈大小</h4><p>选择数组表示栈内容意味着必须预先估计栈的最大容量。容量设大了浪费内存，设小了（没有检测机制）可能溢出。于是需要修改数组实现，动态调整数组 a[] 的大小，使它既能保存所有元素，又不至于浪费过多空间。原理很简单，实现一个方法将栈移动到另一个大小不同的数组中（C++ 中的 Vector 的实现类似）。</p>
<p><strong>添加reSize()方法</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div></pre></td><td class="code"><pre><div class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">reSize</span><span class="params">(<span class="keyword">int</span> max)</span></span>&#123;</div><div class="line">    Item[] temp = (Item[]) <span class="keyword">new</span> Object[max];</div><div class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; N; i++)&#123;</div><div class="line">        temp[i] = a[i];</div><div class="line">    &#125;</div><div class="line">    a = temp;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<p><strong>修改push()方法</strong></p>
<p>在 push() 中检查数组大小：通过检查栈大小 N 和数组大小 a.length 是否相等来检查数组是否能添加新元素。若没有多余空间，则将数组空间加倍。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div></pre></td><td class="code"><pre><div class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">push</span><span class="params">(Item item)</span></span>&#123;</div><div class="line">    <span class="keyword">if</span>(N == a.length) reSize(<span class="number">2</span> * a.length);</div><div class="line">    a[N++] = item;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<p><strong>修改pop()方法</strong></p>
<p>在 pop() 中首先删除栈顶元素，然后检测如果数组太大就将长度<strong>减半</strong>。检测条件是<strong>栈大小是否小于数组的四分之一</strong>。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div></pre></td><td class="code"><pre><div class="line"><span class="function"><span class="keyword">public</span> String <span class="title">pop</span><span class="params">()</span></span>&#123;</div><div class="line">    String item = a[--N];</div><div class="line">    a[N] = <span class="keyword">null</span>; <span class="comment">//避免对象游离</span></div><div class="line">    <span class="keyword">if</span>(N &gt; <span class="number">0</span> &amp;&amp; N == a.length / <span class="number">4</span>) reSize(a.length / <span class="number">2</span>);</div><div class="line">    <span class="keyword">return</span> item;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<p>在这个实现中，栈永远不会溢出，使用率也永远不会低于四分之一（除非栈为空）</p>
<blockquote>
<p>对象游离：Java 垃圾收集策略是回收所有无法被访问的对象的内存。在上面的 pop() 中，被弹出的元素的<strong>引用</strong>仍然存在于数组中，这个元素已经是<strong>孤儿</strong>了，但垃圾收集器无法这点，除非引用被覆盖。即使用例已不再需要这个元素，数组中引用仍然可以让它继续存在。这种情况（保存一个不需要的对象的引用）成为<em>游离</em>。避免对象的游离很容易，只需将被弹出的元素的值设为 null 即可，这将覆盖无用的引用并使系统可以在用例用完被弹出的元素后回收它的内存。</p>
</blockquote>
<h4 id="4-迭代"><a href="#4-迭代" class="headerlink" title="4 迭代"></a>4 迭代</h4><p>集合类数据类型基本操作之一就是，能够使用 Java 的 foreach 语句通过迭代遍历并处理集合中的每个元素。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div></pre></td><td class="code"><pre><div class="line">Iterator&lt;String&gt; i =collection.iterator();</div><div class="line"><span class="keyword">while</span>(i.hasNext())&#123;</div><div class="line">    String s = i.next();</div><div class="line">    <span class="comment">//...</span></div><div class="line">&#125;</div></pre></td></tr></table></figure>
<p>上述代码说明任意可迭代的集合数据类型中必须实现的东西：</p>
<ul>
<li>实现一个 iterator() 方法并返回一个 Iterator 对象</li>
<li>Iterator 类必须包含两个方法：hasNext()（返回一个布尔值）和next() （返回集合中的一个泛型元素）</li>
</ul>
<p>在 Java 中，使用接口机制来指定一个类所必须实现的方法。要使一个类可迭代，需如下步骤：</p>
<ol>
<li><p>声明中加入 <code>implements Iterabe&lt;Item&gt;</code>，对应的接口（<code>java.lang.Iterable</code>）为：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">interface</span> <span class="title">Iterable</span>&lt;<span class="title">Item</span>&gt;</span>&#123;</div><div class="line">    <span class="function">Iterator&lt;Item&gt; <span class="title">iterator</span><span class="params">()</span></span>;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
</li>
<li><p>类中添加 <code>iterator()</code> 方法并返回一个<code>迭代器 Iterator&lt;Item&gt;</code>。迭代器都是泛型的。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div></pre></td><td class="code"><pre><div class="line"><span class="function"><span class="keyword">public</span> Iterator&lt;Item&gt; <span class="title">iteraotr</span><span class="params">()</span></span>&#123;</div><div class="line">    <span class="keyword">return</span> <span class="keyword">new</span> ReverseArrayIterator();</div><div class="line">&#125;</div></pre></td></tr></table></figure>
</li>
<li><p>迭代器是实现了hasNext()和next()方法的类的对象，由下面接口定义（<code>java.util.Iterator</code>）:</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">interface</span> <span class="title">Iterator</span>&lt;<span class="title">Item</span>&gt;</span>&#123;</div><div class="line">    <span class="function"><span class="keyword">boolean</span> <span class="title">hasNext</span><span class="params">()</span></span>;</div><div class="line">    <span class="function">Item <span class="title">next</span><span class="params">()</span></span>;</div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">remove</span><span class="params">()</span></span>;<span class="comment">//不实现</span></div><div class="line">&#125;</div></pre></td></tr></table></figure>
</li>
</ol>
<p>自定义的迭代器（逆序遍历）：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">private</span> <span class="class"><span class="keyword">class</span> <span class="title">ReverseArrayIterator</span> <span class="keyword">implements</span> <span class="title">Iterator</span>&lt;<span class="title">Item</span>&gt;</span>&#123;</div><div class="line">    <span class="keyword">private</span> <span class="keyword">int</span> i = N;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">hasNext</span><span class="params">()</span></span>&#123;</div><div class="line">        <span class="keyword">return</span> i &gt; <span class="number">0</span> ;</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> Item <span class="title">next</span><span class="params">()</span></span>&#123;</div><div class="line">        <span class="keyword">return</span> a[--i];</div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<h4 id="5-下压（LIFO）栈（能够动态调整数组大小的完整实现）："><a href="#5-下压（LIFO）栈（能够动态调整数组大小的完整实现）：" class="headerlink" title="5 下压（LIFO）栈（能够动态调整数组大小的完整实现）："></a>5 下压（LIFO）栈（能够动态调整数组大小的完整实现）：</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">ResizingArrayStack</span>&lt;<span class="title">Item</span>&gt; <span class="keyword">implements</span> <span class="title">Iterable</span>&lt;<span class="title">Item</span>&gt;</span>&#123;</div><div class="line">    <span class="keyword">private</span> Item[] a = (Item[]) <span class="keyword">new</span> Object[<span class="number">1</span>];</div><div class="line">    <span class="keyword">private</span> <span class="keyword">int</span> N = <span class="number">0</span>;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isEmpty</span><span class="params">()</span></span>&#123;</div><div class="line">        <span class="keyword">return</span> N == <span class="number">0</span>;</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">size</span><span class="params">()</span></span>&#123;</div><div class="line">        <span class="keyword">return</span> N;</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">push</span><span class="params">(Item item)</span></span>&#123;</div><div class="line">        <span class="keyword">if</span>(N == a.length)&#123;</div><div class="line">            reSize(<span class="number">2</span> * a.length);</div><div class="line">        &#125;</div><div class="line">        a[N++] = item;</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> Item <span class="title">pop</span><span class="params">()</span></span>&#123;</div><div class="line">        Item item = a[--N];</div><div class="line">        a[N] = <span class="keyword">null</span>;</div><div class="line">        <span class="keyword">if</span>(N &gt; <span class="number">0</span> &amp;&amp; N == a.length / <span class="number">4</span>)&#123;</div><div class="line">            reSize(a.length / <span class="number">2</span>);</div><div class="line">        &#125;</div><div class="line">        <span class="keyword">return</span> item;</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">reSize</span><span class="params">(<span class="keyword">int</span> max)</span></span>&#123;</div><div class="line">        Item[] temp = (Item[]) <span class="keyword">new</span> Obecjt[max];</div><div class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; N; i++)&#123;</div><div class="line">            temp[i] = a[i];</div><div class="line">        &#125;</div><div class="line">        a = temp;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">public</span> Iterator&lt;Item&gt; <span class="title">iterator</span><span class="params">()</span></span>&#123;</div><div class="line">        <span class="keyword">return</span> <span class="keyword">new</span> ReverseArrayIterator();</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="keyword">private</span> <span class="class"><span class="keyword">class</span> <span class="title">ReverseArrayIterator</span> <span class="keyword">implements</span> <span class="title">Iterator</span>&lt;<span class="title">Item</span>&gt;</span>&#123;</div><div class="line">        <span class="keyword">public</span> <span class="keyword">int</span> i = N;</div><div class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">hasNext</span><span class="params">()</span></span>&#123; <span class="keyword">return</span> i &gt; <span class="number">0</span>;&#125;</div><div class="line">        <span class="function"><span class="keyword">public</span> Item <span class="title">next</span><span class="params">()</span></span>&#123; <span class="keyword">return</span> a[--i];&#125;</div><div class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">remove</span><span class="params">(Item item)</span></span>&#123;&#125;</div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<blockquote>
<p>该泛型可迭代Stack API的实现是所有集合类抽象数据类型实现的模板。它将所有元素保存在数组中，并动态调整数组大小以保持数组大小和栈大小之比小于一个常数。</p>
</blockquote>
<h3 id="链表"><a href="#链表" class="headerlink" title="链表"></a>链表</h3><blockquote>
<p>链表：是一种<strong>递归的数据结构</strong>，它或者为空（null），或者是指向一个结点（node）的引用，该节点含有一个泛型的元素和一个指向另一条链表的引用。</p>
</blockquote>
<h4 id="1-结点记录"><a href="#1-结点记录" class="headerlink" title="1 结点记录"></a>1 结点记录</h4><p>用一个<strong>嵌套类</strong>定义节点的抽象数据类型：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">private</span> <span class="class"><span class="keyword">class</span> <span class="title">Node</span></span>&#123;</div><div class="line">    Item item;</div><div class="line">    Node next;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<h4 id="2-构造链表"><a href="#2-构造链表" class="headerlink" title="2 构造链表"></a>2 构造链表</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div></pre></td><td class="code"><pre><div class="line">Node first = <span class="keyword">new</span> Node();</div><div class="line">first.item = <span class="string">"to"</span>;</div><div class="line">Node second = <span class="keyword">new</span> Node();</div><div class="line">second.item = <span class="string">"be"</span>;</div><div class="line">first.next = second;</div><div class="line">Node third = <span class="keyword">new</span> Node();</div><div class="line">third.item = <span class="string">"or"</span>;</div><div class="line">second.next = third;</div></pre></td></tr></table></figure>
<h4 id="3-在表头插入结点"><a href="#3-在表头插入结点" class="headerlink" title="3 在表头插入结点"></a>3 在表头插入结点</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div></pre></td><td class="code"><pre><div class="line">Node oldFirst = first;</div><div class="line">first = <span class="keyword">new</span> Node();</div><div class="line">first.item = <span class="string">"not"</span>;</div><div class="line">first.next = oldFirst;</div></pre></td></tr></table></figure>
<h4 id="4-在表头删除结点"><a href="#4-在表头删除结点" class="headerlink" title="4 在表头删除结点"></a>4 在表头删除结点</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div></pre></td><td class="code"><pre><div class="line">first = first.next;</div></pre></td></tr></table></figure>
<h4 id="5-在表尾插入结点"><a href="#5-在表尾插入结点" class="headerlink" title="5 在表尾插入结点"></a>5 在表尾插入结点</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div></pre></td><td class="code"><pre><div class="line">Node oldLast = last;</div><div class="line">last = <span class="keyword">new</span> Node();</div><div class="line">last.item = <span class="string">"to"</span>;</div><div class="line">oldLast.next = last;</div></pre></td></tr></table></figure>
<h4 id="6-在其它位置的插入和删除结点"><a href="#6-在其它位置的插入和删除结点" class="headerlink" title="6 在其它位置的插入和删除结点"></a>6 在其它位置的插入和删除结点</h4><p>例如：怎样删除链表的尾结点呢？目前唯一方法是遍历整条链表并找出指向 last 的结点，所需时间和链表长度成正比。</p>
<blockquote>
<p><strong>实现任意插入和删除操作的标准解决方案是使用双向链表</strong></p>
</blockquote>
<h4 id="7-链表的遍历"><a href="#7-链表的遍历" class="headerlink" title="7 链表的遍历"></a>7 链表的遍历</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">for</span>(Node x = first; x ! = <span class="keyword">null</span>; x = x.next)&#123;</div><div class="line">    <span class="comment">//处理 x.item</span></div><div class="line">&#125;</div></pre></td></tr></table></figure>
<h4 id="8-链式栈的实现"><a href="#8-链式栈的实现" class="headerlink" title="8 链式栈的实现"></a>8 链式栈的实现</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">Stack</span>&lt;<span class="title">Item</span>&gt;</span>&#123;</div><div class="line">    <span class="keyword">private</span> <span class="class"><span class="keyword">class</span> <span class="title">Node</span></span>&#123;</div><div class="line">        Item item;</div><div class="line">        Node next;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="keyword">private</span> <span class="keyword">int</span> N;</div><div class="line">    <span class="keyword">private</span> Node first;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isEmpty</span><span class="params">()</span></span>&#123;</div><div class="line">        <span class="keyword">return</span> N == <span class="number">0</span>;</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">size</span><span class="params">()</span></span>&#123;</div><div class="line">        <span class="keyword">return</span> N;</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">push</span><span class="params">(Item item)</span></span>&#123;</div><div class="line">        Node oldFirst = first;</div><div class="line">        first.item = item;</div><div class="line">        first.next = oldFirst;</div><div class="line">        N++;</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> Item <span class="title">pop</span><span class="params">()</span></span>&#123;</div><div class="line">        Item item = first.item;</div><div class="line">        first = first.next;</div><div class="line">        N--;</div><div class="line">        <span class="keyword">return</span> item;</div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<h4 id="9-链式队列的实现"><a href="#9-链式队列的实现" class="headerlink" title="9 链式队列的实现"></a>9 链式队列的实现</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">Queue</span>&lt;<span class="title">Item</span>&gt;</span>&#123;</div><div class="line">    <span class="keyword">private</span> <span class="class"><span class="keyword">class</span> <span class="title">Node</span></span>&#123;</div><div class="line">        Item item;</div><div class="line">        Node next;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    Node first;</div><div class="line">    Node last;</div><div class="line">    <span class="keyword">private</span> <span class="keyword">int</span> N;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isEmpty</span><span class="params">()</span></span>&#123;</div><div class="line">        <span class="keyword">return</span> N == <span class="number">0</span>;</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">size</span><span class="params">()</span></span>&#123;</div><div class="line">        <span class="keyword">return</span> N;</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">enQueue</span><span class="params">(Item item)</span></span>&#123;</div><div class="line">        Node oldLast = last;</div><div class="line">        last = <span class="keyword">new</span> Node();</div><div class="line">        last.item = item;</div><div class="line">        <span class="keyword">if</span>(isEmpty())&#123;</div><div class="line">            first = last;</div><div class="line">        &#125;<span class="keyword">else</span>&#123;</div><div class="line">            oldLast.next = last;</div><div class="line">        &#125;</div><div class="line">        N++;</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> Item <span class="title">deQueue</span><span class="params">()</span></span>&#123;</div><div class="line">        Item item = first.item;</div><div class="line">        first = first.next;</div><div class="line">        <span class="keyword">if</span>(isEmpty())&#123;</div><div class="line">            last = <span class="keyword">null</span>;</div><div class="line">        &#125;</div><div class="line">        N--;</div><div class="line">        <span class="keyword">return</span> item;</div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<blockquote>
<p>注意：enQueue() 中当原链表为空时需将 first 和 last 都指向新结点；deQueue() 中当链表为空时也要更新 last 的值</p>
</blockquote>
<h3 id="背包（Bag）"><a href="#背包（Bag）" class="headerlink" title="背包（Bag）"></a>背包（Bag）</h3><p>用链表实现 Bag 只需将 push() 改为 add() 并去掉 pop() 即可，访问顺序是后进先出但不重要。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div></pre></td><td class="code"><pre><div class="line"><span class="comment">// isEmpty() 和 size() 同 Stack</span></div><div class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">Bag</span>&lt;<span class="title">Item</span>&gt; <span class="keyword">implements</span> <span class="title">Iterable</span>&lt;<span class="title">Item</span>&gt;</span>&#123;</div><div class="line">    <span class="keyword">private</span> <span class="class"><span class="keyword">class</span> <span class="title">Node</span>&lt;<span class="title">Item</span>&gt;</span>&#123;</div><div class="line">        Item item;</div><div class="line">        Node next;</div><div class="line">    &#125;</div><div class="line">    Node first;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">add</span><span class="params">(Item item)</span></span>&#123;</div><div class="line">        Node oldFirst = first;</div><div class="line">        first = <span class="keyword">new</span> Node();</div><div class="line">        first.item = item;</div><div class="line">        first.next = oldFirst;</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> Iterator <span class="title">iterator</span><span class="params">()</span></span>&#123;</div><div class="line">        <span class="keyword">return</span> <span class="keyword">new</span> ListIterator();</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">private</span> <span class="class"><span class="keyword">class</span> <span class="title">ListIterator</span>&lt;<span class="title">Item</span>&gt; <span class="keyword">implements</span> <span class="title">Iterator</span>&lt;<span class="title">Item</span>&gt;</span>&#123;</div><div class="line">        <span class="comment">//不直接使用first，单独保存一个引用，避免覆盖 first</span></div><div class="line">        <span class="keyword">private</span> Node current = first;</div><div class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">hasNext</span><span class="params">()</span></span>&#123;</div><div class="line">            <span class="keyword">return</span> current != <span class="keyword">null</span>;</div><div class="line">        &#125;</div><div class="line">        <span class="function"><span class="keyword">public</span> Item <span class="title">next</span><span class="params">()</span></span>&#123;</div><div class="line">            Item item = current.item;</div><div class="line">            current = current.next;</div><div class="line">            <span class="keyword">return</span> item;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<div class="table-container">
<table>
<thead>
<tr>
<th>数据结构</th>
<th>优  点</th>
<th>缺  点</th>
</tr>
</thead>
<tbody>
<tr>
<td> 数组</td>
<td>通过索引可以直接访问任意元素</td>
<td>在初始化时就要知道元素的数量</td>
</tr>
<tr>
<td> 链表</td>
<td>使用的空间大小和元素数量成正比</td>
<td>需要通过引用访问任意元素</td>
</tr>
</tbody>
</table>
</div>
<p>在研究新问题时，采用以下步骤识别目标并使用数据抽象解决问题：</p>
<ul>
<li>定义API</li>
<li>根据特定应用场景开发用例代码</li>
<li>描述一种数据结构（一组值的表示），并在 API 所对应的抽象数据类型的实现中根据它定义类的实例变量</li>
<li>描述算法（实现一组操作的方式），并根据它实现类中实例方法</li>
<li>分析算法性能</li>
</ul>
<p>以后用到的一些数据结构：</p>
<div class="table-container">
<table>
<thead>
<tr>
<th>数据结构</th>
<th>抽象数据类型</th>
<th>数据表示</th>
</tr>
</thead>
<tbody>
<tr>
<td> 父链接树</td>
<td>UnionFind</td>
<td>整形数组</td>
</tr>
<tr>
<td> 二分查找树</td>
<td>BST</td>
<td>含有两个链接的结点</td>
</tr>
<tr>
<td> 字符串</td>
<td>String</td>
<td>数组、偏移量和长度</td>
</tr>
<tr>
<td> 二叉堆</td>
<td>PQ</td>
<td>对象数组</td>
</tr>
<tr>
<td> 散列表（拉链表）</td>
<td>SeparateChainingHashSH</td>
<td>链表数组</td>
</tr>
<tr>
<td> 散列表（线性探测法）</td>
<td>LinearProbingHashST</td>
<td>两个对象数组</td>
</tr>
<tr>
<td> 图的邻接链表</td>
<td>Graph</td>
<td>Bag 对象的数组</td>
</tr>
<tr>
<td> 单词查找树</td>
<td>TrieST</td>
<td>含有链接数组的结点</td>
</tr>
<tr>
<td> 三向单词查找树</td>
<td>TST</td>
<td>含有三个链接的结点</td>
</tr>
</tbody>
</table>
</div>
<h3 id="Q-amp-A-1"><a href="#Q-amp-A-1" class="headerlink" title="Q&amp;A"></a>Q&amp;A</h3><ol>
<li>不是所有语言都支持泛型，其它替代方案：<ul>
<li>为每种类型数据都实现一个不同集合数据类型</li>
<li>构造一个 Object 对象的栈，并在 pop() 时进行类型转换。缺点是类型不匹配错误只能在运行时发现，而在泛型中可在编译期发现。</li>
</ul>
</li>
<li>Java不允许泛型数组？<br> 详细了解 <strong>共变数组（convariant array）</strong> 和 <strong>类型擦除（type erasure）</strong></li>
<li>创建一个字符串栈的数组：<br> <code>Stack&lt;String&gt;[] a = (Stack&lt;String&gt;[]) new Stack[N];</code> 使用泛型时，Java会在编译时检查类型安全性，但会在运行时抛弃所有这些信息。因此运行时右侧语句变为 <code>Stack&lt;Object&gt;[]</code> 或只剩下 <code>Stack[N]</code>，故需要类型转换。</li>
<li>为什么将 Node 声明为嵌套类？为什么用 private？<br> 这样可以将 Node 的方法和实例变量的访问范围限制在包含它的类中。<strong>私有嵌套类</strong>另一个特点是只有包含它的类能直接访问它的实例变量，因此不用将它的实例变量声明为 public 或 private。<em>非静态的嵌套类也被称为内部类</em></li>
<li>运行 <code>javac Stack.java</code> 生成 <code>Stack.class</code> 和 <code>Stack$Node.class</code>？<br> 后者是内部类 Node 创建的，Java 中 <code>$</code>分隔外部类和内部类。</li>
<li>能否向栈或队列添加空（null）元素？<br> Java中很常见（如 Stack 和 List 允许，但测试发现 Queue 似乎不允许）。</li>
<li>若在迭代中用 push() 或 pop()，Stack 的迭代器怎么办？<br> 抛 <code>java.util.ConcurrentModificationException</code></li>
<li>foreach 循环可以访问数组，但不能访问 String？<br> String 没有实现 Iterable 接口。</li>
<li>为什么不设计一个通用的 Collection 实现添加元素、删除最近插入元素、删除最早插入的元素、删除随机元素、迭代、返回集合元素数量等？<br> 使用<strong>窄接口</strong>而不是<strong>宽接口</strong>，原因是无法保证高效实现所有方法，并且分开设计更简单，代码更易懂。</li>
</ol>

      
    </div>
    
    
    

    

    
      <div>
        <div style="padding: 10px 0; margin: 20px auto; width: 90%; text-align: center;">
  <div>请我喝杯咖啡吧☕~</div>
  <button id="rewardButton" disable="enable" onclick="var qr = document.getElementById('QR'); if (qr.style.display === 'none') {qr.style.display='block';} else {qr.style.display='none'}">
    <span>打赏</span>
  </button>
  <div id="QR" style="display: none;">

    
      <div id="wechat" style="display: inline-block">
        <img id="wechat_qr" src="/images/wechatpay.jpg" alt="Fighter. 微信支付"/>
        <p>微信支付</p>
      </div>
    

    
      <div id="alipay" style="display: inline-block">
        <img id="alipay_qr" src="/images/alipay.jpg" alt="Fighter. 支付宝"/>
        <p>支付宝</p>
      </div>
    

    

  </div>
</div>

      </div>
    

    
      <div>
        <ul class="post-copyright">
  <li class="post-copyright-author">
    <strong>本文作者：</strong>
    Fighter.
  </li>
  <li class="post-copyright-link">
    <strong>本文链接：</strong>
    <a href="http://fighterhit.github.io/2017/12/27/algorithm_and_datastructure/Algorithms4/Ch1-Fundamentals/" title="（一）基础（Fundamentals）：数据结构">http://fighterhit.github.io/2017/12/27/algorithm_and_datastructure/Algorithms4/Ch1-Fundamentals/</a>
  </li>
  <li class="post-copyright-license">
    <strong>版权声明： </strong>
    本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/3.0/" rel="external nofollow" target="_blank">CC BY-NC-SA 3.0</a> 许可协议。转载请注明出处！
  </li>
</ul>

      </div>
    

    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/tags/算法/" rel="tag"># 算法</a>
          
            <a href="/tags/Algorithms-Notes/" rel="tag"># Algorithms Notes</a>
          
        </div>
      

      
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/2017/12/26/algorithm_and_datastructure/二分查找/" rel="next" title="你真的会二分查找吗？">
                <i class="fa fa-chevron-left"></i> 你真的会二分查找吗？
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/2017/12/30/algorithm_and_datastructure/Algorithms4/Ch1-Fundamentals-Time-Complexity/" rel="prev" title="（二）基础（Fundamentals）：算法分析">
                （二）基础（Fundamentals）：算法分析 <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>



    <div class="post-spread">
      
        <!-- JiaThis Button BEGIN -->
<div class="jiathis_style">
<span class="jiathis_txt">分享到：</span>
<a class="jiathis_button_fav">收藏夹</a>
<a class="jiathis_button_tsina">新浪微博</a>
<a class="jiathis_button_qzone">QQ空间</a>
<a class="jiathis_button_weixin">微信</a>
<a class="jiathis_button_cqq">腾讯QQ</a>
<a class="jiathis_button_copy">复制网址</a>
<a class="jiathis_button_share">一键分享</a>

<a href="http://www.jiathis.com/share?uid=2140465" class="jiathis jiathis_txt jiathis_separator jtico jtico_jiathis" target="_blank">更多</a>
<a class="jiathis_counter_style"></a>
</div>
<script type="text/javascript" >
var jiathis_config={
  data_track_clickback:true,
  summary:"",
  shortUrl:false,
  hideMore:false
}
</script>
<script type="text/javascript" src="http://v3.jiathis.com/code/jia.js?uid=" charset="utf-8"></script>
<!-- JiaThis Button END -->
      
    </div>
  </div>


          </div>
          


          
  
    <div class="comments" id="comments">
      <div id="lv-container" data-id="city" data-uid="MTAyMC8zMjY0Ni85MjA3"></div>
    </div>
  


        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview-wrap">
            站点概览
          </li>
        </ul>
      

      <section class="site-overview-wrap sidebar-panel">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <img class="site-author-image" itemprop="image"
                src="/images/avatar.jpg"
                alt="Fighter." />
            
              <p class="site-author-name" itemprop="name">Fighter.</p>
              <p class="site-description motion-element" itemprop="description">学习 | 分享 | 交流 | 进步</p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/archives/">
              
                  <span class="site-state-item-count">26</span>
                  <span class="site-state-item-name">日志</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-categories">
                <a href="/categories/index.html">
                  <span class="site-state-item-count">6</span>
                  <span class="site-state-item-name">分类</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-tags">
                <a href="/tags/index.html">
                  <span class="site-state-item-count">28</span>
                  <span class="site-state-item-name">标签</span>
                </a>
              </div>
            

          </nav>

          

          <div class="links-of-author motion-element">
            
              
                <span class="links-of-author-item">
                  <a href="https://github.com/fighterhit" target="_blank" title="GitHub">
                    
                      <i class="fa fa-fw fa-github"></i>GitHub</a>
                </span>
              
                <span class="links-of-author-item">
                  <a href="https://weibo.com/fighterhit" target="_blank" title="Weibo">
                    
                      <i class="fa fa-fw fa-weibo"></i>Weibo</a>
                </span>
              
            
          </div>

          
          

          
          

          

        </div>
      </section>

      
      <!--noindex-->
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
              
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#1-基础编程模型"><span class="nav-number">1.</span> <span class="nav-text">1 基础编程模型</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#Java-四类八种类型"><span class="nav-number">1.1.</span> <span class="nav-text">Java 四类八种类型</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#数组"><span class="nav-number">1.2.</span> <span class="nav-text">数组</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#静态方法"><span class="nav-number">1.3.</span> <span class="nav-text">静态方法</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#输入输出"><span class="nav-number">1.4.</span> <span class="nav-text">输入输出</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#Q-amp-A"><span class="nav-number">1.5.</span> <span class="nav-text">Q&amp;A</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#2-数据抽象"><span class="nav-number">2.</span> <span class="nav-text">2 数据抽象</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#使用抽象数据类型"><span class="nav-number">2.1.</span> <span class="nav-text">使用抽象数据类型</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#抽象数据类型举例"><span class="nav-number">2.2.</span> <span class="nav-text">抽象数据类型举例</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#数据类型的设计"><span class="nav-number">2.3.</span> <span class="nav-text">数据类型的设计</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#3-背包、队列和栈"><span class="nav-number">3.</span> <span class="nav-text">3 背包、队列和栈</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#API"><span class="nav-number">3.1.</span> <span class="nav-text">API</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#举例：算术表达式求值"><span class="nav-number">3.1.1.</span> <span class="nav-text">举例：算术表达式求值</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#集合数据类型的实现"><span class="nav-number">3.2.</span> <span class="nav-text">集合数据类型的实现</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#1-定容栈"><span class="nav-number">3.2.1.</span> <span class="nav-text">1 定容栈</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#2-进一步：泛型栈"><span class="nav-number">3.2.2.</span> <span class="nav-text">2 进一步：泛型栈</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#3-动态调整栈大小"><span class="nav-number">3.2.3.</span> <span class="nav-text">3 动态调整栈大小</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#4-迭代"><span class="nav-number">3.2.4.</span> <span class="nav-text">4 迭代</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#5-下压（LIFO）栈（能够动态调整数组大小的完整实现）："><span class="nav-number">3.2.5.</span> <span class="nav-text">5 下压（LIFO）栈（能够动态调整数组大小的完整实现）：</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#链表"><span class="nav-number">3.3.</span> <span class="nav-text">链表</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#1-结点记录"><span class="nav-number">3.3.1.</span> <span class="nav-text">1 结点记录</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#2-构造链表"><span class="nav-number">3.3.2.</span> <span class="nav-text">2 构造链表</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#3-在表头插入结点"><span class="nav-number">3.3.3.</span> <span class="nav-text">3 在表头插入结点</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#4-在表头删除结点"><span class="nav-number">3.3.4.</span> <span class="nav-text">4 在表头删除结点</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#5-在表尾插入结点"><span class="nav-number">3.3.5.</span> <span class="nav-text">5 在表尾插入结点</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#6-在其它位置的插入和删除结点"><span class="nav-number">3.3.6.</span> <span class="nav-text">6 在其它位置的插入和删除结点</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#7-链表的遍历"><span class="nav-number">3.3.7.</span> <span class="nav-text">7 链表的遍历</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#8-链式栈的实现"><span class="nav-number">3.3.8.</span> <span class="nav-text">8 链式栈的实现</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#9-链式队列的实现"><span class="nav-number">3.3.9.</span> <span class="nav-text">9 链式队列的实现</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#背包（Bag）"><span class="nav-number">3.4.</span> <span class="nav-text">背包（Bag）</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#Q-amp-A-1"><span class="nav-number">3.5.</span> <span class="nav-text">Q&amp;A</span></a></li></ol></li></ol></div>
            

          </div>
        </section>
      <!--/noindex-->
      

      
      
    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; 2016 - <span itemprop="copyrightYear">2018</span>
  <span class="with-love">
    <i class="fa fa-home"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">Fighter.</span>

  
</div>









        
<div class="busuanzi-count">
  <!--<script async src="https://dn-lbstatics.qbox.me/busuanzi/2.3/busuanzi.pure.mini.js"></script>-->
  <script async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>

  
    <span class="site-uv">
      <i class="fa fa-user"></i>
      <span class="busuanzi-value" id="busuanzi_value_site_uv"></span>
      
    </span>
  

  
    <span class="site-pv">
      <i class="fa fa-eye"></i>
      <span class="busuanzi-value" id="busuanzi_value_site_pv"></span>
      
    </span>
  

    <span class="site-pv">&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;&nbsp;
    Hosted by <a target="_blank" href="https://github.com/">GitHub Pages</a>
    </span>

</div>







        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>

  
  <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>

  
  <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>

  
  <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>

  
  <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>

  
  <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.3"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.3"></script>



  
  


  <script type="text/javascript" src="/js/src/affix.js?v=5.1.3"></script>

  <script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.1.3"></script>



  
  <script type="text/javascript" src="/js/src/scrollspy.js?v=5.1.3"></script>
<script type="text/javascript" src="/js/src/post-details.js?v=5.1.3"></script>



  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.3"></script>



  


  




	





  





  
    <script type="text/javascript">
      (function(d, s) {
        var j, e = d.getElementsByTagName(s)[0];
        if (typeof LivereTower === 'function') { return; }
        j = d.createElement(s);
        j.src = 'https://cdn-city.livere.com/js/embed.dist.js';
        j.async = true;
        e.parentNode.insertBefore(j, e);
      })(document, 'script');
    </script>
  








  





  

  
<script>
(function(){
    var bp = document.createElement('script');
    var curProtocol = window.location.protocol.split(':')[0];
    if (curProtocol === 'https') {
        bp.src = 'https://zz.bdstatic.com/linksubmit/push.js';        
    }
    else {
        bp.src = 'http://push.zhanzhang.baidu.com/push.js';
    }
    var s = document.getElementsByTagName("script")[0];
    s.parentNode.insertBefore(bp, s);
})();
</script><!-- hexo-inject:begin --><!-- hexo-inject:end -->


  

  
  


  

  

</body>
</html>
